/*
 *  Copyright (C) 2010 Martin Haulrich <mwh.isv@cbs.dk> and Matthias Buch-Kromann <mbk.isv@cbs.dk>
 *
 *  This file is part of the IncrementalParser package.
 *
 *  The IncrementalParser program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.osdtsystem.incparser.parsers;

import java.util.List;
import org.osdtsystem.incparser.featureextraction.FeatureExtractor;
import org.osdtsystem.incparser.featureextraction.MstFeatureExtractorLabelled;
import org.osdtsystem.incparser.featureextraction.MstFeatureExtractorUnlabelled;
import org.osdtsystem.incparser.features.FeatureAggregatorScore;
import org.osdtsystem.incparser.features.FeatureHandler;
import org.osdtsystem.incparser.features.WeightVector;
import org.osdtsystem.incparser.graphs.BaseGraph;
import org.osdtsystem.incparser.graphs.ConllAdapter;
import org.osdtsystem.incparser.mst.ChuLiuEdmonds;

/**
 * 
 * @author Martin Haulrich and Matthias Buch-Kromann
 */
public class MstParserLabelled extends AbstractMstParser {
    public MstParserLabelled(FeatureHandler edgeTypeHandler,
            FeatureHandler stringHandler, FeatureHandler featureHandler) {
        super(edgeTypeHandler, stringHandler, featureHandler);
    }

    @Override
    FeatureExtractor[][] featureExtractorGroups(ConllAdapter graph) {
        FeatureExtractor[] labelledMstExtractorGroup = {labelledMstExtractor(graph)};
        FeatureExtractor[] unlabelledMstExtractorGroup = {unlabelledMstExtractor(graph)};
        FeatureExtractor[][] extractorGroups = {unlabelledMstExtractorGroup, labelledMstExtractorGroup};
        return extractorGroups;
    }

    int packLabelScore(int node, int type, boolean headBeforeDep, int types) {
        return 2 * (node * types + type) + (headBeforeDep ? 1 : 0);
    }

    @Override
    public ConllAdapter parse( WeightVector weights, ConllAdapter graph) {
        // Remove edges from graph and compute number of nodes and edge types
        graph.clearEdges();
        BaseGraph baseGraph = graph.baseGraph();
        int nodes = graph.nodes(baseGraph);
        int types = edgeTypeHandler.features();

        // Create MST extractors and score aggregator for computing scores
        MstFeatureExtractorLabelled labelledExtractor = labelledMstExtractor(graph);
        MstFeatureExtractorUnlabelled unlabelledExtractor = unlabelledMstExtractor(graph);
        FeatureAggregatorScore aggregator = new FeatureAggregatorScore(weights, featureHandler, 0);

        // Compute label scores
        int labelledScoreCount = nodes * types * 2;
        float[] labelledHeadScore = new float[labelledScoreCount];
        float[] labelledDepScore = new float[labelledScoreCount];
        boolean[] falseTrue = {false, true};
        for (boolean headBeforeDep : falseTrue) {
            for (int node = 0; node < nodes; node++) {
                for (int type = 0; type < types; type++) {
                    int packed = packLabelScore(node, type, headBeforeDep, types);

                    // Dependent score
                    aggregator.clear();
                    labelledExtractor.extractDependentFeatures(aggregator, baseGraph, node, type, headBeforeDep);
                    labelledDepScore[packed] = (float) aggregator.score();

                    // Head score
                    aggregator.clear();
                    labelledExtractor.extractHeadFeatures(aggregator, baseGraph, node, type, headBeforeDep);
                    labelledHeadScore[packed] = (float) aggregator.score();
                }
            }
        }

        // Compute edge-factored scores and best label for each dependency
        double[][] scores = new double[nodes][nodes];
        int[][] label = new int[nodes][nodes];
        for (int head = 0; head < nodes; head++) {
            for (int node = 0; node < nodes; node++) {
                // Find unlabelled score
                aggregator.clear();
                unlabelledExtractor.extractDependency(aggregator, baseGraph, node, head);
                double unlabelledScore = aggregator.score();

                // Find best edge type for dependency
                int bestType = 0;
                float bestLabelScore = Float.NEGATIVE_INFINITY;
                boolean headBeforeDep = head < node;
                for (int type = 0; type < types; ++type) {
                    float labelScore = labelledDepScore[packLabelScore(node, type, headBeforeDep, types)]
                            + labelledHeadScore[packLabelScore(node, type, headBeforeDep, types)];
                    if (labelScore > bestLabelScore) {
                        bestLabelScore = labelScore;
                        bestType = type;
                    }
                }
                label[head][node] = bestType;
                scores[head][node] = unlabelledScore + bestLabelScore;
            }
        }

        // Parse sentence and add edges to graph
        List<Integer> CLEheads = ChuLiuEdmonds.chuLiuEdmonds(scores);
        for (int node = 1; node < nodes; ++node) {
            int head = CLEheads.get(node);
            graph.addEdge(node, head, label[head][node]);
        }

        // Return parse
        return graph;
    }
}
